/*
 * [51] 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
 * 即输出P%1000000007
 *
 * 输入
 * 1,2,3,4,5,6,7,0
 * 输出
 * 7 （指静态下构成的逆序对，而非任意组合构成的逆序对，如这里只有1,0
 * 2,0...而没有2,1）
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
 private:
  long result;

 public:
  int InversePairs(vector<int> data) {
    result = 0;
    if (data.empty()) return 0;
    // 从大到小，归并排序，并统计逆序对个数
    mergeSort(data, 0, data.size() - 1);
    // 取模输出，防止输出太大
    return result % 1000000007;
  }

  /**
   * @brief mergeSort()用于分治，将一个无序数组分治成一个size为1的数组
   *
   * @param a
   * @param begin
   * @param end data.size() - 1
   */
  void mergeSort(vector<int>& a, int begin, int end) {
    // 递归的出口
    if (begin >= end) return;
    int mid = begin + (end - begin) / 2;
    // 左子树组排序
    mergeSort(a, begin, mid);
    // 右子树组排序
    mergeSort(a, mid + 1, end);
    // 归并有序数组
    merge(a, begin, mid, end);
  }

  /**
   * @brief 用于合并，分治后将有序子数组合并成一个有序数组
   *
   * @param a
   * @param begin
   * @param mid
   * @param end
   */
  void merge(vector<int>& a, int begin, int mid, int end) {
    // 开辟临时数组 9-0=9 用于存放有序数组
    vector<int> temp(end - begin + 1);
    // 左子数组，右子数组，临时数组起始索引
    int i = begin, j = mid + 1, k = 0;
    // 注意范围
    while (i <= mid && j <= end) {
      if (a[i] > a[j]) {
        // 这里从大到小排序，方便判断逆序对
        temp[k++] = a[i++];
        // 合并的是有序子数组（从大到小），故a[i]>a[j]时，也有a[i]>a[j]~a[end],均可构成逆序对（a[i]在左边，a[j]在右边）
        // 存在逆序对的情况计数
        result += end - j + 1;
      } else {
        temp[k++] = a[j++];
      }
    }

    // 如果左右子数有一方提前到达右边界
    // 即j先到达end+1，剩下的i<=mid,此时剩下的a[i]都小于已经放入temp[k]的数了，而此时a[i]已经有序直接一次放入
    while (i <= mid) temp[k++] = a[i++];
    // 反之
    while (j <= end) temp[k++] = a[j++];

    // 复制临时数组元素到原数组
    for (int i = begin, k = 0; i <= end && k < temp.size(); i++, k++) {
      a[i] = temp[k];
    }
  }
};

int main() {
  class Solution solute;
  vector<int> arra1 = {1, 33, 5, 1, 2};
  vector<int> arra2 = {2, 11, 0};
  int result1 = solute.InversePairs(arra1);
  int result2 = solute.InversePairs(arra2);

  cout << "sum1: " << result1 << endl;
  cout << "sum2: " << result2 << endl;

  return 0;
}

// @lc code=end
